package com.tgy.algorithm.base;

import java.util.Arrays;

public class _二分法练习 {

    // 1 2 2 3 4 5 5
    // value = 5
    // 找到 value >=  最左的index
    public static int findLeftLeValue(int nums[], int value) {

        if (nums == null || nums.length == 0) {
            return -1;
        }

        int left = 0,right = nums.length - 1;
        int mid;
        int result = -1;
        while (left <= right) {
            // 这里一定要加一个括号，保证先执行 >>
            mid = left + ((right - left) >> 1);
            if(nums[mid] >= value) {
                result = mid;
                right = mid - 1;
            }else  {
                left = mid + 1;
            }
        }

        return result;
    }

    public static int[] randomAdjacentNotEqual(int max, int count) {

        int[] nums = new int[count];
        int i = 0;
        while (i < count) {
            // 1 到 max
            int num = (int) ((Math.random() * max) + 1);
            if(i > 0 && num == nums[i - 1]) {
                continue;
            }
            nums[i++] = num;
        }

        return nums;
    }

    public static int localMin(int[] nums) {

        if (nums == null || nums.length == 0) {
            return -1;
        }

        if (nums.length == 1) {
            return 0;
        }

        if(nums[0] < nums[1]) {
            return 0;
        }

        int length = nums.length;
        if(nums[length-2] > nums[length - 1]) {
            return length - 1;
        }

//        3 2 3 2 3
        int left = 0, right = length - 1;
        // 必须保证有三个数进行比较，才能保证下面的mid-1不会越界
        while (left < right - 1) {
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < nums[mid+1] && nums[mid] < nums[mid-1]) {
                return mid;
            }else if(nums[mid] > nums[mid - 1]) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }

        return nums[left] > nums[right] ? right : left;
    }

    public static int localMin01(int[] nums) {

        if (nums == null || nums.length == 0) {
            return -1;
        }

        if (nums.length == 1) {
            return 0;
        }

        if(nums[0] < nums[1]) {
            return 0;
        }

        if(nums[nums.length-1] < nums[nums.length-2]) {
            return nums.length - 1;
        }

        int left = 1, right = nums.length - 2;
        int mid = 0;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            if(nums[mid] < nums[mid+1] && nums[mid] < nums[mid-1]) {
                return mid;
            }else if(nums[mid] > nums[mid -1]) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }

        return -1;
    }

    public static boolean check(int[] nums,int index) {

        if(nums == null || nums.length == 0) {
            return false;
        }

        if(index >= nums.length) {
            return false;
        }

        if (index  == 0) {
            return nums[0] < nums[1];
        }
        if(index == nums.length - 1) {
            return nums[index] < nums[nums.length - 2];
        }

        return nums[index] < nums[index - 1] && nums[index] < nums[index+1];
    }

    public static void main(String[] args) {
        //  1 2 2 3 4 5 5
//        int result = findLeftLeValue(new int[] {1, 2, 2, 3, 4, 5, 5 }, 100);
//        System.out.println(result);
        for (int i = 0;i < 10000;i++) {
            int[] nums = randomAdjacentNotEqual(200, 100);
            int result = localMin(nums);
//            System.out.println(result);
//            System.out.println();
            if(!check(nums,result)) {
                System.out.println(Arrays.toString(nums));
                System.err.println(result);
            }
        }

    }
}
